{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Steps to Reduce a Number in Binary Representation to One"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSteps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将二进制表示减到 1 的步骤数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个以二进制形式表示的数字 <code>s</code> 。请你返回按下述规则将其减少到 1 所需要的步骤数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>\n",
    "\t<p>如果当前数字为偶数，则将其除以 2 。</p>\n",
    "\t</li>\n",
    "\t<li>\n",
    "\t<p>如果当前数字为奇数，则将其加上 1 。</p>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>题目保证你总是可以按上述规则将测试用例变为 1 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;1101&quot;\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>&quot;1101&quot; 表示十进制数 13 。\n",
    "Step 1) 13 是奇数，加 1 得到 14&nbsp;\n",
    "Step 2) 14 是偶数，除 2 得到 7\n",
    "Step 3) 7  是奇数，加 1 得到 8\n",
    "Step 4) 8  是偶数，除 2 得到 4&nbsp; \n",
    "Step 5) 4  是偶数，除 2 得到 2&nbsp;\n",
    "Step 6) 2  是偶数，除 2 得到 1&nbsp; \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;10&quot;\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>&quot;10&quot; 表示十进制数 2 。\n",
    "Step 1) 2 是偶数，除 2 得到 1 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;1&quot;\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length&nbsp;&lt;= 500</code></li>\n",
    "\t<li><code>s</code> 由字符 <code>&#39;0&#39;</code> 或 <code>&#39;1&#39;</code> 组成。</li>\n",
    "\t<li><code>s[0] == &#39;1&#39;</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-steps-to-reduce-a-number-in-binary-representation-to-one](https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-steps-to-reduce-a-number-in-binary-representation-to-one](https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1101\"', '\"10\"', '\"1\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        n, ans = len(s), 0\n",
    "        meet1 = False\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0':\n",
    "                ans += 2 if meet1 else 1\n",
    "            else:\n",
    "                if not meet1:\n",
    "                    if i != 0:\n",
    "                        ans += 2\n",
    "                    meet1 = True\n",
    "                else:\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        # num,n,ans=0,len(s),0\n",
    "        # for i in range(n):\n",
    "        #     num+=int(s[n-1-i])*2**i\n",
    "        num=int(s,2)\n",
    "        ans=0\n",
    "        if num==1:return 0\n",
    "        while num!=1:\n",
    "            if num%2==0:\n",
    "                # num=num/2 /会转换为浮点数，有误差\n",
    "                num=num//2\n",
    "                # num=num>>1\n",
    "            else:\n",
    "                num+=1\n",
    "            ans+=1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        carry, res = 0, 0\n",
    "        for i in range(len(s)-1, 0, -1):\n",
    "            res = res+2 if carry ^ (s[i] == '1') else res+1\n",
    "            carry = 1 if carry or (s[i] == '1') else 0\n",
    "        return res+1 if carry else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i]=='1':break\n",
    "        if i==0:\n",
    "            return len(s)-1\n",
    "        zero=s[:i].count('0')\n",
    "        return zero+len(s)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        count_trailing_zeros = len(s) - len(s.rstrip('0'))\n",
    "\n",
    "       #计算尾0\n",
    "        count_trailing_zeros = len(s) - len(s.rstrip('0'))\n",
    "\n",
    "        # 去尾0\n",
    "        s = s.rstrip('0')\n",
    "        #字符串长度\n",
    "        length = len(s)\n",
    "        if length > 1:\n",
    "            #计算0的个数\n",
    "            count_ones = s.count(\"0\")\n",
    "\n",
    "            return count_ones+length+1+count_trailing_zeros\n",
    "        else :\n",
    "            return count_trailing_zeros"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        num = int(s, 2)\n",
    "        res = 0\n",
    "        while num > 1:\n",
    "            res += 1\n",
    "            if num % 2 == 1:\n",
    "                num += 1\n",
    "            else:\n",
    "                num //= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        num=int(s,2)\n",
    "        res=0\n",
    "        while num>1:\n",
    "            if num%2==0:\n",
    "                num//=2\n",
    "            else:\n",
    "                num+=1\n",
    "            res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        s1=int(s,2)\n",
    "        i=0\n",
    "        while s1>1:\n",
    "            if s1&1:\n",
    "                s1+=1\n",
    "            else:\n",
    "                s1>>=1\n",
    "            i+=1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        for i in range(n-1,0,-1):\n",
    "            if s[i]=='1':\n",
    "                return s[:i].count('0')+n+1\n",
    "        return n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        count_trailing_zeros = len(s) - len(s.rstrip('0'))\n",
    "\n",
    "        # 计算二进制数的长度\n",
    "        s = s.rstrip('0')\n",
    "        \n",
    "        length = len(s)\n",
    "        if length > 1:\n",
    "        # 创建一个全为1的字符串\n",
    "            ones_string = \"1\" * length\n",
    "\n",
    "            # 将全为1的字符串转换为整数\n",
    "            ones_as_int = int(ones_string, 2)\n",
    "\n",
    "            # 将原始二进制数转换为整数\n",
    "            binary_as_int = int(s, 2)\n",
    "\n",
    "            # 计算补码\n",
    "            twos_complement = ones_as_int - binary_as_int\n",
    "\n",
    "            # 将补码转换为二进制字符串\n",
    "            twos_complement_binary = bin(twos_complement)\n",
    "\n",
    "            count_ones = twos_complement_binary.count(\"1\")\n",
    "\n",
    "            return count_ones+length+1+count_trailing_zeros\n",
    "        else :\n",
    "            return count_trailing_zeros"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        res = 0\n",
    "        num = int(s, 2)\n",
    "        while num > 1:\n",
    "            if num & 1:\n",
    "                num += 1\n",
    "            else:\n",
    "                num >>= 1\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        for i in range(len(s)-1,0,-1):\n",
    "            if s[i]=='1':\n",
    "                # zero=s[:i].count('0')\n",
    "                return s[:i].count('0')+len(s)+1\n",
    "        else:\n",
    "            return len(s)-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        meet = False\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == '0':\n",
    "                ans += (2 if meet else 1)\n",
    "            else:\n",
    "                if not meet:\n",
    "                    if i != 0:\n",
    "                        ans += 2\n",
    "                    meet = True\n",
    "                else:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        def add_(s):\n",
    "            res = ''\n",
    "            index = -1\n",
    "            for i in range(len(s)-1,-1,-1):\n",
    "                if s[i] == '0':\n",
    "                    index=i\n",
    "                    break\n",
    "            if index == -1:\n",
    "                for i in range(len(s)):\n",
    "                    res += '0'\n",
    "                res = '1' + res\n",
    "            else:\n",
    "                for i in range(len(s)-1-index):\n",
    "                    res += '0'\n",
    "                res = s[:index]+'1'+res\n",
    "            return res\n",
    "        cnt = 0\n",
    "        while s != '1':\n",
    "            if s[-1] == '1':\n",
    "                s = add_(s)\n",
    "            else:\n",
    "                s = s[:-1]\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        s = int(s, 2)\n",
    "        while s != 1:\n",
    "            if s & 1:\n",
    "                s += 1\n",
    "            else:\n",
    "                s >>= 1\n",
    "            ans += 1\n",
    "            # print(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        t = s.rstrip('0')\n",
    "        res = len(s)-len(t)\n",
    "        if t == '1': return res\n",
    "        return len(t) + t.count('0') + 1 + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        s = int(s,2)\n",
    "        cout = 0\n",
    "        while(s != 1):\n",
    "            if s % 2 != 0:\n",
    "                s += 1\n",
    "                cout += 1\n",
    "                continue\n",
    "            else:\n",
    "                s //= 2\n",
    "                cout += 1\n",
    "        return cout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        # nums = [int(ch) for ch in s[::-1]]\n",
    "        # res = mod = 0\n",
    "        # for i in nums[:-1]:\n",
    "        #     cur, mod = (i+mod) % 2, (i+mod) // 2\n",
    "        #     res += cur + 1\n",
    "        #     if cur:\n",
    "        #         mod = 1\n",
    "        # return res if mod + nums[-1] == 1 else res + 1\n",
    "\n",
    "        # -------------------\n",
    "        res = 0\n",
    "        n = int(s, base=2)\n",
    "        while n != 1:\n",
    "            res += 1\n",
    "            if n % 2:\n",
    "                n += 1\n",
    "            else:\n",
    "                n //= 2\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        num = int(\"0b\" + s, 2)\n",
    "        ans = 0\n",
    "        while num != 1:\n",
    "            if num % 2:\n",
    "                num += 1\n",
    "            else:\n",
    "                num //= 2\n",
    "\n",
    "            ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        # num,n,ans=0,len(s),0\n",
    "        # for i in range(n):\n",
    "        #     num+=int(s[n-1-i])*2**i\n",
    "        num=int(s,2)\n",
    "        ans=0\n",
    "        if num==1:return 0\n",
    "        while num!=1:\n",
    "            if num%2==0:\n",
    "                # num=num/2 /会转换为浮点数，精度下降\n",
    "                num=num//2\n",
    "            else:\n",
    "                num+=1\n",
    "            ans+=1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        steps = 0\n",
    "        while ''.join(s) != '1':\n",
    "            if s[-1] == '1':\n",
    "                s.insert(0, '0')\n",
    "                for x in range(len(s)-1, -1, -1):\n",
    "                    if s[x] == '1':\n",
    "                        s[x] = '0'\n",
    "                    else:\n",
    "                        s[x] = '1'\n",
    "                        break\n",
    "                if s[0] == '0':\n",
    "                    s.pop(0)\n",
    "            else:\n",
    "                s = s[:-1]\n",
    "            steps += 1\n",
    "        return steps\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, ss: str) -> int:\n",
    "        s = 0\n",
    "        for ch in ss:\n",
    "            if ch == '1':\n",
    "                s = s * 2 + 1\n",
    "            else:\n",
    "                s = 2 * s\n",
    "        ans = 0\n",
    "        while s != 1:\n",
    "            if s & 1:\n",
    "                s += 1\n",
    "                s //= 2\n",
    "                ans += 2\n",
    "            else:\n",
    "                s //= 2\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        num = 0\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            num += int(s[i])*(2**(len(s) -1 - i))\n",
    "        ans = 0\n",
    "        while num != 1:\n",
    "            if num % 2:\n",
    "                num += 1\n",
    "            else:\n",
    "                num = num//2\n",
    "            ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        # num = int(s,2)\n",
    "        # times = 0\n",
    "        # while num != 1:\n",
    "        #     if num % 2==0:\n",
    "        #         num = num //2\n",
    "        #     else:\n",
    "        #         num +=1\n",
    "        #     times +=1\n",
    "        \n",
    "        # return times\n",
    "        n,ans = len(s),0\n",
    "        carry = False\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i] == '0':\n",
    "                ans+= (2 if carry else 1)\n",
    "            else:\n",
    "                if carry:\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    if i !=0:\n",
    "                        ans+=2\n",
    "                    carry = True\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 遍历计数\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        n, ans = len(s), 0\n",
    "        # meet1 记录我们有没有遇见过字符 1\n",
    "        meet1 = False\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0':\n",
    "                # 如果当前字符为 0，分为两种情况\n",
    "                # (1) 还没有遇见过字符 1，那么这个 0 是字符串低位的 0，需要一次除二操作\n",
    "\n",
    "                # (2) 遇见过字符 1，那么这个 0 会因为它右侧的某次加一操作变为 1，因此它需要一次加一和一次除二操作\n",
    "                ans += (2 if meet1 else 1)\n",
    "            else:\n",
    "                # 如果当前字符为 1，分为两种情况\n",
    "                # (1) 还没有遇见过字符 1，那么这个 1 需要一次加一和一次除二操作\n",
    "                #     这里需要考虑一种特殊情况，就是这个 1 是字符串最左侧的 1，它并不需要任何操作\n",
    "\n",
    "                # (2) 遇见过字符 1，那么这个 1 会因为它右侧的某次加一操作变为 0，因此它只需要一次除二操作\n",
    "                if not meet1:\n",
    "                    if i != 0:\n",
    "                        ans += 2\n",
    "\n",
    "                    meet1 = True\n",
    "                else:\n",
    "                    ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 模拟\n",
    "    def numSteps2(self, s: str) -> int:\n",
    "        num = int(\"0b\" + s, 2)\n",
    "        ans = 0\n",
    "        while num != 1:\n",
    "            if num % 2:\n",
    "                num += 1\n",
    "            else:\n",
    "                num //= 2\n",
    "\n",
    "            ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = int(s,base = 2)\n",
    "        while n != 1:\n",
    "            if n % 2 == 0:\n",
    "                n //= 2\n",
    "            else:\n",
    "                n += 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        nums = [int(ch) for ch in s[::-1]]\n",
    "        res = mod = 0\n",
    "        for i in nums[:-1]:\n",
    "            cur, mod = (i+mod) % 2, (i+mod) // 2\n",
    "            res += cur + 1\n",
    "            if cur:\n",
    "                mod = 1\n",
    "        return res if mod + nums[-1] == 1 else res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        add = 0\n",
    "        res = 0\n",
    "        isOK = False\n",
    "        for x in reversed(s[1:]):\n",
    "            if x == '1':\n",
    "                isOK = True\n",
    "                break\n",
    "        if not isOK:\n",
    "            s = s[1:]\n",
    "        # print(s)\n",
    "        for x in reversed(s):\n",
    "            if x == '0' and add == 0:\n",
    "                res += 1\n",
    "            elif x == '0' and add == 1:\n",
    "                res += 2\n",
    "            elif x == '1' and add == 0:\n",
    "                res += 2\n",
    "                add = 1\n",
    "            elif x == '1' and add == 1:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        res = 0\n",
    "        i = len(s)-1\n",
    "        while i>0 and s[i]=='0':\n",
    "            res += 1\n",
    "            i -= 1\n",
    "        while i>0:\n",
    "            j = i-1\n",
    "            while j>-1 and s[j]=='1':\n",
    "                res += 1\n",
    "                j -= 1\n",
    "            res += 2\n",
    "            i = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        res = 0\n",
    "        i = len(s)-1\n",
    "        while i>0 and s[i]=='0':\n",
    "            res += 1\n",
    "            i -= 1\n",
    "        while i>0:\n",
    "            j = i-1\n",
    "            while j>-1 and s[j]=='1':\n",
    "                res += 1\n",
    "                j -= 1\n",
    "            res += 2\n",
    "            i = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        n, ans = len(s), 0\n",
    "        # meet1 记录我们有没有遇见过字符 1\n",
    "        meet1 = False\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0':\n",
    "                # 如果当前字符为 0，分为两种情况\n",
    "                # (1) 还没有遇见过字符 1，那么这个 0 是字符串低位的 0，需要一次除二操作\n",
    "                # (2) 遇见过字符 1，那么这个 0 会因为它右侧的某次加一操作变为 1，因此它需要一次加一和一次除二操作\n",
    "                ans += (2 if meet1 else 1)\n",
    "            else:\n",
    "                # 如果当前字符为 1，分为两种情况\n",
    "                # (1) 还没有遇见过字符 1，那么这个 1 需要一次加一和一次除二操作\n",
    "                #     这里需要考虑一种特殊情况，就是这个 1 是字符串最左侧的 1，它并不需要任何操作\n",
    "                # (2) 遇见过字符 1，那么这个 1 会因为它右侧的某次加一操作变为 0，因此它只需要一次除二操作\n",
    "                if not meet1:\n",
    "                    if i != 0:\n",
    "                        ans += 2\n",
    "                    meet1 = True\n",
    "                else:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        n, ans = len(s), 0\n",
    "        meet1 = False\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0':\n",
    "                ans += (2 if meet1 else 1)\n",
    "            else:\n",
    "                if not meet1:\n",
    "                    if i != 0:\n",
    "                        ans += 2\n",
    "                    meet1 = True\n",
    "                else:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        a = [ch for ch in s]\n",
    "        count = 0\n",
    "        while len(a) > 1:\n",
    "            if a[-1] == '0':\n",
    "                a.pop()\n",
    "                count += 1\n",
    "            else:\n",
    "                count += 1\n",
    "                while len(a) > 0 and a[-1] == '1':\n",
    "                    a.pop()\n",
    "                    count += 1\n",
    "                if len(a) > 0:\n",
    "                    a[-1] = '1'\n",
    "                else:\n",
    "                    a.append('1')\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        num = int(s,2)\n",
    "        times = 0\n",
    "        while num != 1:\n",
    "            if num % 2==0:\n",
    "                num = num //2\n",
    "            else:\n",
    "                num +=1\n",
    "            times +=1\n",
    "        \n",
    "        return times\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        steps = 0\n",
    "        while ''.join(s) != '1':\n",
    "            if s[-1] == '1':\n",
    "                s.insert(0, '0')\n",
    "                for x in range(len(s)-1, -1, -1):\n",
    "                    if s[x] == '1':\n",
    "                        s[x] = '0'\n",
    "                    else:\n",
    "                        s[x] = '1'\n",
    "                        break\n",
    "                if s[0] == '0':\n",
    "                    s.pop(0)\n",
    "            else:\n",
    "                s = s[:-1]\n",
    "            steps += 1\n",
    "        return steps\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        # num,n,ans=0,len(s),0\n",
    "        # for i in range(n):\n",
    "        #     num+=int(s[n-1-i])*2**i\n",
    "        num=int(s,2)\n",
    "        ans=0\n",
    "        if num==1:return 0\n",
    "        while num!=1:\n",
    "            if num%2==0:\n",
    "                # num=num/2 /会转换为浮点数，精度下降\n",
    "                # num=num//2\n",
    "                num=num>>1\n",
    "            else:\n",
    "                num+=1\n",
    "            ans+=1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        num = int(s,base=2)\n",
    "        ans = 0\n",
    "        while num > 1:\n",
    "            if num & 1:\n",
    "                num += 1\n",
    "            else:\n",
    "                num >>= 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        num = int(s, 2)  # 将二进制字符串转换为整数\n",
    "        steps = 0  # 用于计算步骤数的变量\n",
    "\n",
    "        while num != 1:\n",
    "            if num % 2 == 0:  # 如果数字是偶数\n",
    "                num = num // 2  # 除以2\n",
    "            else:  # 如果数字是奇数\n",
    "                num = num + 1  # 加1\n",
    "            steps += 1  # 增加步骤数\n",
    "\n",
    "        return steps\n",
    "\n",
    "# 创建一个Solution对象\n",
    "solution = Solution()\n",
    "\n",
    "# 使用测试用例来测试方法\n",
    "print(solution.numSteps('1101'))  # 输出应该是步骤数，例如，在这个测试用例下输出应为 6\n",
    "print(solution.numSteps('10'))  # 输出应该是 1\n",
    "print(solution.numSteps('1'))  # 输出应该是 0，因为已经是 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, ss: str) -> int:\n",
    "        s = int(ss, 2)\n",
    "        ans = 0\n",
    "        while s != 1:\n",
    "            if s & 1:\n",
    "                s += 1\n",
    "                s //= 2\n",
    "                ans += 2\n",
    "            else:\n",
    "                s //= 2\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        for i in range(n-1,0,-1):\n",
    "            if s[i]=='1':\n",
    "                # zero=s[:i].count('0')\n",
    "                return s[:i].count('0')+n+1\n",
    "        else:\n",
    "            return n-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        a = list(s)\n",
    "        count = 0\n",
    "        while len(a) > 1:\n",
    "            if a[-1] == '0':\n",
    "                a.pop()\n",
    "                count += 1\n",
    "            else:\n",
    "                count += 1\n",
    "                while len(a) > 0 and a[-1] == '1':\n",
    "                    a.pop()\n",
    "                    count += 1\n",
    "                if len(a) > 0:\n",
    "                    a[-1] = '1'\n",
    "                else:\n",
    "                    a.append('1')\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        sa=int(s,2)\n",
    "        total=0\n",
    "        while 1:\n",
    "            if sa == 1:\n",
    "                return total\n",
    "            elif sa%2 == 0:\n",
    "                sa//=2\n",
    "                total+=1\n",
    "            else:\n",
    "                sa+=1\n",
    "                total+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            if s == '1':\n",
    "                break\n",
    "            n = len(s)\n",
    "            if s[-1] == '1':\n",
    "                j = n-1\n",
    "                while j >= 0 and s[j] == '1':\n",
    "                    j -= 1\n",
    "                if j == -1:\n",
    "                    cnt += 1+n\n",
    "                    break\n",
    "                else:\n",
    "                    cnt += n-j\n",
    "                    s = s[:j]+'1'\n",
    "            else:\n",
    "                j = n-1\n",
    "                while j >= 0 and s[j] == '0':\n",
    "                    j -= 1\n",
    "                cnt += (n-1-j)\n",
    "                if j == -1:\n",
    "                    break\n",
    "                else:\n",
    "                    s = s[:j+1]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        num = int(s, 2)  # 将二进制字符串转换为整数\n",
    "        steps = 0  # 用于计算步骤数的变量\n",
    "\n",
    "        while num != 1:\n",
    "            if num % 2 == 0:  # 如果数字是偶数\n",
    "                num = num // 2  # 除以2\n",
    "            else:  # 如果数字是奇数\n",
    "                num = num + 1  # 加1\n",
    "            steps += 1  # 增加步骤数\n",
    "\n",
    "        return steps\n",
    "\n",
    "# 创建一个Solution对象\n",
    "solution = Solution()\n",
    "\n",
    "# 使用测试用例来测试方法\n",
    "print(solution.numSteps('1101'))  # 输出应该是步骤数，例如，在这个测试用例下输出应为 6\n",
    "print(solution.numSteps('10'))  # 输出应该是 1\n",
    "print(solution.numSteps('1'))  # 输出应该是 0，因为已经是 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        c = 0\n",
    "        ans = 0\n",
    "        n = 0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if s[i] == '0' and c == 0:\n",
    "                c = 0\n",
    "                ans += 1\n",
    "            elif s[i] == '0' and c == 1:\n",
    "                c = 1\n",
    "                ans += 2\n",
    "            elif s[i] == '1' and c == 0:\n",
    "                c = 1\n",
    "                ans += 2\n",
    "            elif s[i] == '1' and c == 1:\n",
    "                ans += 1\n",
    "            if s[i] == '1':\n",
    "                n += 1\n",
    "        if n == 1:\n",
    "            return len(s) - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        steps = 0\n",
    "        while ''.join(s) != '1':\n",
    "            if s[-1] == '1':\n",
    "                s.insert(0, '0')\n",
    "                for x in range(len(s)-1, -1, -1):\n",
    "                    if s[x] == '1':\n",
    "                        s[x] = '0'\n",
    "                    else:\n",
    "                        s[x] = '1'\n",
    "                        break\n",
    "                if s[0] == '0':\n",
    "                    s.pop(0)\n",
    "            else:\n",
    "                s = s[:-1]\n",
    "            steps += 1\n",
    "        return steps\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        for i in range(n-1,0,-1):\n",
    "            if s[i]=='1':\n",
    "                # zero=s[:i].count('0')\n",
    "                return s[:i].count('0')+n+1\n",
    "        else:\n",
    "            return n-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        remain = 0\n",
    "        res = 0\n",
    "        for i in reversed(range(1, n)):\n",
    "            total = int(s[i]) + remain\n",
    "            if total == 0:\n",
    "                res += 1\n",
    "                remain = 0\n",
    "            elif total == 1:\n",
    "                res += 2\n",
    "                remain = 1\n",
    "            elif total == 2:\n",
    "                res += 1\n",
    "                remain = 1\n",
    "        if remain > 0:\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        num = int(s, 2)  # 将二进制字符串转换为整数\n",
    "        steps = 0  # 用于计算步骤数的变量\n",
    "\n",
    "        while num != 1:\n",
    "            if num % 2 == 0:  # 如果数字是偶数\n",
    "                num = num // 2  # 除以2\n",
    "            else:  # 如果数字是奇数\n",
    "                num = num + 1  # 加1\n",
    "            steps += 1  # 增加步骤数\n",
    "\n",
    "        return steps\n",
    "\n",
    "# 创建一个Solution对象\n",
    "solution = Solution()\n",
    "\n",
    "# 使用测试用例来测试方法\n",
    "print(solution.numSteps('1101'))  # 输出应该是步骤数，例如，在这个测试用例下输出应为 6\n",
    "print(solution.numSteps('10'))  # 输出应该是 1\n",
    "print(solution.numSteps('1'))  # 输出应该是 0，因为已经是 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        carry, res = 0, 0\n",
    "        for i in range(len(s)-1, 0, -1):\n",
    "            res = res+2 if carry ^ (s[i] == '1') else res+1\n",
    "            carry = 1 if carry or (s[i] == '1') else 0\n",
    "        return res+1 if carry else res\n",
    "\n",
    "\n",
    "        \n",
    "        # #转数字\n",
    "        # n = int(s, 2)\n",
    "        # count = 0\n",
    "        # while n != 1:\n",
    "        #     if n&1:\n",
    "        #         count += 2\n",
    "        #     else:\n",
    "        #         count += 1\n",
    "        #     n = (n+1)>>1\n",
    "        # return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        # 模拟\n",
    "        num = int(s, 2)\n",
    "        res = 0\n",
    "        while num != 1:\n",
    "            if num % 2 == 0:\n",
    "                num //= 2\n",
    "            else:\n",
    "                num += 1\n",
    "            res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        strs, cnt = list(s), 0\n",
    "        while len(strs) > 1:\n",
    "            if strs[-1] == '0':\n",
    "                strs.pop()\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "                while len(strs) > 0 and strs[-1] == '1':\n",
    "                    strs.pop()\n",
    "                    cnt += 1\n",
    "                if len(strs) > 0:\n",
    "                    strs[-1] = '1'\n",
    "                else:\n",
    "                    strs.append('1')\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        x=n-1\n",
    "        ans=0\n",
    "        while s[x]=='0':\n",
    "            ans+=1\n",
    "            x-=1\n",
    "        if x==0:\n",
    "            return ans\n",
    "        k=0\n",
    "        while x>-1:\n",
    "            while x>-1 and s[x]=='1':\n",
    "                x-=1\n",
    "                k+=1\n",
    "            ans+=1+k\n",
    "            if x==-1:\n",
    "                return ans\n",
    "            k=-1\n",
    "            while x>-1 and s[x]=='0':\n",
    "                x-=1\n",
    "                k+=1\n",
    "            ans+=k*2\n",
    "            k=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        s = int(s, 2)\n",
    "        while s != 1:\n",
    "            if s&1:\n",
    "                s += 1\n",
    "            else:\n",
    "                s //= 2\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        for i in range(n-1,0,-1):\n",
    "            if s[i]=='1':\n",
    "                return s[:i].count('0')+n+1\n",
    "        else:\n",
    "            return n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSteps(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        tmp = [s[x] for x in range(l-1, -1, -1)]\n",
    "        asn = i = 0\n",
    "        while i < len(tmp) - 1:\n",
    "            if tmp[i] == '0':\n",
    "                asn += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                asn += 1\n",
    "                j = i\n",
    "                while j < l and tmp[j] == '1':\n",
    "                    tmp[j] = '0'\n",
    "                    j += 1\n",
    "                if l == j:\n",
    "                    tmp.append('1')\n",
    "                else:\n",
    "                    tmp[j] = '1'\n",
    "        return asn"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
